package com.js.study.datastructs.tree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author JiangSen
 * @DATE 2023/12/27 14:05
 */
public class TreeNodeOne<E extends Comparable<E>> {
    //内部定义节点类
    private class Node<E>{
        E e;
        Node<E> left;
        Node<E> right;
        public Node(E e){
            this.e = e;
            this.left = null;
            this.right=null;
        }
    }
    private Node<E> root;
    private int size;
    public TreeNodeOne(){
        this.root = null;
        this.size = 0;
    }
    public int getSize(){
        return size;
    }
    public boolean isEmpty(){
        return size==0;
    }

    //add
    public void add(E e){
        this.root = add(this.root,e);
    }
    public Node<E> add(Node<E> node,E input){
        if(node == null){
            size++;
            return  new Node<>(input);
        }
        if(input.compareTo(node.e)<0 ){
            node.left = add(node.left,input);
        }else if(input.compareTo(node.e)>0 ){
            node.right = add(node.right,input);
        }else{
            return node;
        }
        return node;
    }
    //get
    public boolean get(E e){
        return contain(root,e);
    }
    public boolean contain(Node<E> node, E e){
        if(node == null){
            return false;
        }
        if(e.compareTo(node.e)<0){
            return contain(node.left,e);
        }else if(e.compareTo(node.e)>0){
            return contain(node.right,e);
        }else{
            return true;
        }
    }
    //遍历二叉树
    //前序遍历: 根左右    中序遍历:左根右   后序遍历:左右根
    public void preOrder(){
        preOrder(root);
    }
    public void midOrder(){
        midOrder(root);
    }
    public void lastOrder(){
        lastOrder(root);
    }
    private void preOrder(Node<E> node){
        if(node == null){
            return;
        }
        System.out.println(node.e + "\t");
        preOrder(node.left);
        preOrder(node.right);
    }
    //使用stack 方式实现
    public void preOrderStack(){
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            Node current = stack.pop();//弹出root节点
            System.out.println(current.e);
            if(current.right !=null){
                stack.push(current.right);
            }
            if(current.left!=null){
                stack.push(current.left);
            }
        }
    }

    //中序遍历  左  根  右
    public void midOrderStack(){
        Stack<Node> stack = new Stack<>();
        Node<E> current = root;
        while(current !=null || !stack.isEmpty()){
            while(current != null){
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            System.out.println(current.e +"");
            current = current.right;
        }
    }

    //后续遍历
    public void lastOrderStack(){
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        Stack<Node> stackTemp = new Stack<>();
        while(!stack.isEmpty()){
            Node current = stack.pop();
            stackTemp.push(current);
            if(current.left!=null){
                stack.push(current.left);
            }
            if(current.right!=null){
                stack.push(current.right);
            }
        }
        while(!stackTemp.isEmpty()){
            Node current = stackTemp.pop();
            System.out.println(current.e+" ");
        }
    }

    private void midOrder(Node<E> node){
        if(node == null){
            return;
        }
        midOrder(node.left);
        System.out.println(node.e + "\t");
        midOrder(node.right);
    }
    private void lastOrder(Node<E> node){
        if(node == null){
            return;
        }
        lastOrder(node.left);
        lastOrder(node.right);
        System.out.println(node.e + "\t");
    }
    //bfs  广度优先搜索遍历
    public void levelOrder(){
        Queue<Node<E>> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            Node<E> current = queue.remove();
            System.out.println(current.e+" ");
            if(current.left !=null){
                queue.add(current.left);
            }
            if(current.right != null){
                queue.add(current.right);
            }
        }
    }

//从root 开始 找到树的最小节点  并且返回值
    public E getMinNode(){
        if(isEmpty()){
            throw new RuntimeException("tree is null,do not search");
        }
        return getMinNode(root).e;
    }
    private Node<E> getMinNode(Node<E> node){
        if(node.left == null){
            return node;
        }else{
            return getMinNode(node.left);
        }
    }
    public E removeMinNode() {
        E minValue = getMinNode();
        root = removeMinNode(root);//2.删最小后返回
        return minValue;//1.最小节点即删除节点，数据返回
    }

    private Node<E> removeMinNode(Node<E> node){
        if(node.left == null){
            Node deleteNode = node.right;
            node.right = null;
            size--;
            return deleteNode;
        }
        node.left = removeMinNode(node.left);
        return node;
    }
    public E getMaxNode() {
        if (getSize() == 0) {
            throw new RuntimeException("空树无效");
        }
        return getMaxNode(root).e;
    }

    public Node<E> getMaxNode(Node<E> node) {
        if (node.right == null) {
            return node;
        } else {
            return getMaxNode(node.right);
        }
    }

    public E removeMaxNode() {
        E maxValue = getMaxNode();
        root = removeMaxNode(root);
        return maxValue;
    }

    private Node<E> removeMaxNode(Node<E> node) {
        if (node.right == null) {
            Node deleteNode_leftNode = node.left;
            node.left = null;
            size--;
            return deleteNode_leftNode;
        }
        node.right = removeMaxNode(node.right);
        return node;
    }
    public static void main(String[] args) {
        TreeNodeOne one = new TreeNodeOne<>();
//        one.add(5);
//        one.add(3);
//        one.add(6);
//        one.add(8);
//        one.add(4);
//        one.add(2);
        one.add(5);
        one.add(1);
        one.add(7);
        one.add(2);
        one.add(4);
        //one.add(3);
//        System.out.println("size="+one.size);
//        System.out.println("-----前序遍历");
//        //根-左-右
//        one.preOrderStack();
//        System.out.println();
//
//        System.out.println("-----中序遍历");
//        //中序：左-根-右
//        one.midOrderStack();
//        System.out.println();
//
//        System.out.println("-----后序遍历");
        //后序：左-右-根
        //one.lastOrderStack();
        System.out.println();
        //one.levelOrder();
        System.out.println(one.getMinNode());
        System.out.println();
        System.out.println(one.removeMinNode());
        System.out.println();
        one.preOrderStack();
//        System.out.println("-----是否包含");
//        System.out.println(one.get(2));
//        System.out.println(one.get(22));
    }
}
